Comet OJ Contest 75
sooke 这套真是高质量好题 /dz
$A. 绝境$
考虑容斥，答案就是每种 $n - 1$ 个操作的交集减去 $n$ 个操作的交集。求矩形交的前后缀和！
$B. 命运$
注意，边不相交这是个很有用而且很强的条件！这样限定了 $i$ 位置取的 $in_i$ 个点只能是上方的底部和下方的顶端一些点。
特殊性质一是很有启发意义的一档。发现每个点引出的边方向确定了！为什么？若 $p_{i - 1} + 1 = p_i$ 则向右，若 $p_{i - 1} - 1 = p_i$ 则向左。然后可以愉快的dp，$f[i, j]$ 表示到第 $i$ 点处理完后，上方有 $j$ 条边（下方有 $p_i - j$ 条边）
推广一下发现，每个点的入度和出度都定了！为啥啊
- $in_i + out_i = d_i$
- $p_{i - 1} - in_i + out_i = p_i$
然后继续用刚才思路做，枚举上方几条入边和出边：$f[i, j] = \sum_x \sum_y f[i - 1, j - x + y]$
转移是 $n^2$ 的。。。优化：$g[i, j] = \sum\limits_{x = 0}^{in_i} f[i - 1, j + x]$ $f[i, j] = \sum\limits_{y = 0}^{out_i} g[i, j - y]$ 发现都是前缀和形式，前缀和优化。
$C. 终焉$
答案显然是断边数 + 1。
技巧/经典套路1：修改是改变一个点和它周围一圈点时，考虑它的树上结构，只要修改父亲节点处就好了！
集合幂级数？FWT、FMT？？好像都只能做部分分
$f[x, s]$ 表示节点 $x$ 儿子中状态为 $s$ 的数量，发现这样修改和查询一个是 $O(2^m)$，一个是 $O(1)$，这太不均匀了！
经典套路2：分两段，比如说修改 $x$ 值为 $s$，那么 $f[fa, t]++$，其中前半段 $t$ 和 $s$ 相同，后半段 $s$ 是 $t$ 的子集；
查询的话就先 $s = ~s$，$ans += f[fa, t]$，其中后半段 $t$ 和 $s$ 相同，前半段 $t$ 是 $s$ 的子集。但这样时间是 $O(n2^{m / 2})$ 了，空间还是 $O(n2^m)$
经典套路3：度数分块
考虑 $bound$，当度数 $< bound$ 时暴力修改/询问，$> bound$ 时用上面的数组做，发现这样空间复杂度是 $O(n / d * 2^{m / 2})$；发现 $d = 2^{m / 2}$ 时最优！
就做完啦。